Thomassen proved that every planar graph $G$ on $n$ vertices has at least$2^{n/9}$ distinct $L$-colorings if $L$ is a 5-list-assignment for $G$ and atleast $2^{n/10000}$ distinct $L$-colorings if $L$ is a 3-list-assignment for$G$ and $G$ has girth at least five. Postle and Thomas proved that if $G$ is agraph on $n$ vertices embedded on a surface $\Sigma$ of genus $g$, then thereexist constants $\epsilon,c_g > 0$ such that if $G$ has an $L$-coloring, then$G$ has at least $c_g2^{\epsilon n}$ distinct $L$-colorings if $L$ is a5-list-assignment for $G$ or if $L$ is a 3-list-assignment for $G$ and $G$ hasgirth at least five. More generally, they proved that there exist constants$\epsilon,\alpha>0$ such that if $G$ is a graph on $n$ vertices embedded in asurface $\Sigma$ of fixed genus $g$, $H$ is a proper subgraph of $G$, and$\phi$ is an $L$-coloring of $H$ that extends to an $L$-coloring of $G$, then$\phi$ extends to at least $2^{\epsilon(n - \alpha(g + |V(H)|))}$ distinct$L$-colorings of $G$ if $L$ is a 5-list-assignment or if $L$ is a3-list-assignment and $G$ has girth at least five. We prove the same result if$G$ is triangle-free and $L$ is a 4-list-assignment of $G$, where$\epsilon=\frac{1}{8}$, and $\alpha= 130$.
展开▼
机译：托马森证明，如果$ L $是$ G $的5个列表分配且至少$ 2 ^，则$ n $顶点上的每个平面图$ G $至少具有$ 2 ^ {n / 9} $个独特的$ L $颜色。如果$ L $是$ G $的3列表分配，并且$ G $的围长至少为5，则{n / 10000} $不同的$ L $着色。 Postle和Thomas证明，如果$ G $是嵌入在$ g $属的表面$ \ Sigma $上的$ n $顶点上的图，则存在常数$ \ epsilon，c_g> 0 $使得如果$ G $具有$ L $-着色，则如果$ L $是$ G $的5-列表分配，或者$ L $是3-，则$ G $至少具有$ c_g2 ^ {\ epsilon n} $独特的$ L $-着色。 $ G $和$ G $的列表分配至少有五个。更普遍地，他们证明存在常数$ \ epsilon，\ alpha> 0 $，使得如果$ G $是嵌入在固定属$ g $的表面$ \ Sigma $中的$ n $个顶点上的图，则$ H $为适当的$ G $子图，$ \ phi $是$ H $的$ L $颜色，扩展为$ G $的$ L $颜色，然后$ \ phi $至少扩展为$ 2 ^ { \ epsilon（n-\ alpha（g + | V（H）|））}如果$ L $是一个5列表分配或$ L $是a3列表，则$ G $的$ L $着色-assignment和$ G $的周长至少为5。如果$ G $是无三角形且$ L $是$ G $的4个列表赋值，则我们证明了相同的结果，其中$ \ epsilon = \ frac {1} {8} $，而$ \ alpha = 130 $。
展开▼
